/*
 * @lc app=leetcode.cn id=57 lang=cpp
 *
 * [57] 插入区间
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {

        int i = 0;
        while (i < intervals.size() && intervals[i][0] < newInterval[0])
            i++;

        intervals.insert(intervals.begin() + i, newInterval);

        vector<vector<int>> ans;

        vector<int> &curr_v = intervals[0];
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] <= curr_v[1])
            {
                curr_v[1] = max(curr_v[1], intervals[i][1]);
            }
            else
            {
                ans.push_back(curr_v);
                curr_v = intervals[i];
            }
        }
        ans.push_back(curr_v);

        return ans;
    }
};
// @lc code=end
